Markov’s Inq.
$$ P[X \geq t] \leq \frac{\mathbb{E}\left[ X\right]}{t} $$Proof: $$ \begin{aligned} \mathbb{E}\left[ X\right] &= \sum_{i=1}^{+\infty} i \cdot p_X(i) = \sum_{i=1}^{n} i \cdot p_X(i) + \sum_{i=n}^{+\infty} i \cdot p_X(i) \geq \sum_{i=n}^{+\infty} i \cdot p_X(i) \geq n \sum_{i=n}^{+\infty} p_X(i) = n P[X \geq n] \end{aligned} $$
Chebyshev’s Inq.
$$ P[|X - \mu| \geq t] \leq \frac{\sigma^2}{t^2} $$Proof: $$ \begin{aligned} P[X \geq n] &\leq \frac{\mathbb{E}\left[ X\right]}{n} \\ P[X^2 \geq n^2] &\leq \frac{\mathbb{E}\left[ X^2\right]}{n^2} \\ P[(X - \mu)^2 \geq n^2] = P[|X - \mu| \geq n] &\leq \frac{\mathbb{E}\left[ (X - \mu)^2 \right]}{n^2} = \frac{\sigma^2}{n^2} \\ \end{aligned} $$
Chernoff’s Inq.
$$ P[X \geq t] \leq \frac{\mathbb{E}\left[ e^{\lambda X} \right]}{e^{\lambda t}} $$Proof: $$ \begin{aligned} P[X \geq t] &\leq \frac{\mathbb{E}\left[ X\right]}{t} \\ P[X \geq t] &= P[\lambda X \geq \lambda t] \\ &= P[e^{\lambda X} \geq e^{\lambda t}] \\ &\leq \frac{\mathbb{E}\left[ e^{\lambda X} \right]}{e^{\lambda t}} \\ \end{aligned} $$
Chernoff’s Inq. for Sums
$$ P[\overline{X_n} \geq t] \leq \left( \frac{\mathbb{E}\left[ e^{\lambda X_1} \right]}{e^{\lambda t}} \right)^n $$Proof: $$ \begin{aligned} P[\overline{X_n} \geq t] &\leq \frac{\mathbb{E}\left[ e^{n\lambda \overline{X_n}}\right]}{e^{n\lambda t}} \\ &\leq \frac{\mathbb{E}\left[ e^{\lambda \sum_{i=1}^{n}X_i}\right]}{e^{n\lambda t}} \\ &= \frac{\prod_{i=1}^{n}\mathbb{E}\left[ e^{\lambda X_i}\right]}{e^{n\lambda t}} \\ &= \frac{\prod_{i=1}^{n}\mathbb{E}\left[ e^{\lambda X_1}\right]}{e^{n\lambda t}} \\ &= \left( \frac{\mathbb{E}\left[ e^{\lambda X_1} \right]}{e^{\lambda t}} \right)^n \end{aligned} $$